The present invention relates generally to encoding and decoding systems such as data storage systems, data communication systems, etc. More particularly, the present invention pertains to decoding techniques for use in such systems.
Turbo coding (e.g., as described in C. Berrou, A. Glavieux, and P. Thitimajshima, “Near shannon limit error-correcting coding and decoding: Turbo-codes,” in Proc. IEEE Intl. Conf. Commun., (Geneva), pp. 1064–70 (May 1993)) and low-density parity-check (LDPC) coding (e.g., as described in R. G. Gallager, Low-Density Parity-Check Codes, M.I.T. Press (1963) and D. J. C. MacKay and R. Neal, “Near shannon limit performance of low-density parity-check codes,” Electron. Lett., vol. 33, pp. 457–8 (March 1997)) are two powerful coding methods that have received considerable attention recently for their ability to offer large coding gains using practical iterative decoding methods. As first introduced, the encoding of turbo codes was generally much less complex than the encoding of LDPC codes, whereas, the decoding of LDPC codes was much less complex than the decoding of turbo codes. Generally, for example, the complexity referred to herein is measured in the number of mathematical operations required per bit, and does not account for the memory requirements needed in implementation.
Coding schemes have been used which combine the ideas of both turbo coding and LDPC coding. For example, in M. Oberg and P. H. Siegel, “Parity check codes for partial response channels,” Globecom, pp. 717–722 (1999), a single bit parity-check code was used in a configuration similar to serial concatenated turbo coding. Further, parallel concatenated turbo coding was described in L. Ping, S. Chan, and K. L. Yeung, “Iterative decoding of multi-dimensional concatenated single parity check codes,” Proc. IEEE Intl. Conf Commun., vol. 1 of 3, pp. 131–35 (1998) and in H. Sawaguchi and J. K. Wolf, “Turbo decoding for high-rate concatenated parity-check codes on PRML channels,” IEEE Transactions on Magnetics, vol. 36, No. 5, pp. 2173–75 (September 2000), which concatenates in parallel two single bit parity codes and decodes serially.
Data that is coded is typically received at a decoder. The task of a decoder is to reconstruct the original data source (e.g., bit stream) from the coded data, which may have been corrupted by noise.
Coding schemes utilizing both turbo coding and LDPC coding ideas generally result in a less complex encoding process. However, the process of decoding such code, as described in the articles by Ping, et al., and Sawaguchi, et al., is not as simple as is desired. As such, less complex decoding processes for such coding schemes are needed.